package com.sx.sx1.lintcode.day717;

import java.util.HashMap;
import java.util.LinkedList;
import java.util.Map;
import java.util.Queue;

public class LC1235 {



      static class TreeNode {
          public int val;
          public TreeNode left, right;
         public TreeNode(int val) {
              this.val = val;
              this.left = this.right = null;
          }
      }


    static class Solution {
        /**
         * @param data: a string after a tree serializing
         * @return: the tree after a string deserialization
         */
        public TreeNode deserialize(String data) {
            if(data==null || data.length() ==0) return null;
            String[] arr = data.split(",");

            Map<Integer,TreeNode> graph = new HashMap<>();
            for (String s : arr) {
                String[] sarr = s.split("_");
                int pos = Integer.valueOf(sarr[0]);
                int val = Integer.valueOf(sarr[1]);

                graph.put(pos,new TreeNode(val));
            }


            Queue<Integer> qpos = new LinkedList<>();
            Queue<TreeNode> q = new LinkedList<>();
            qpos.add(0);
            q.add(graph.get(0));

            while (!q.isEmpty()){
                TreeNode pop = q.poll();
                int idx= qpos.poll();

                int leftidx = idx*2+1;
                int rightidx = leftidx+1;

                if(graph.containsKey(leftidx)){
                    pop.left = graph.get(leftidx);
                    qpos.add(leftidx);
                    q.add(graph.get(leftidx));
                }

                if(graph.containsKey(rightidx)){
                    pop.right = graph.get(rightidx);
                    qpos.add(rightidx);
                    q.add(graph.get(rightidx));
                }
            }
            return graph.get(0);
        }

        /**
         * @param treeNode: A tree that needs to be serialized
         * @return: the string after a tree serializing
         */
        public String serialize(TreeNode treeNode) {
            StringBuilder sb = new StringBuilder();
            Queue<TreeNode> q = new LinkedList<>();
            Queue<Integer> qpos = new LinkedList<>();
            q.add(treeNode);
            qpos.add(0);

            while (!q.isEmpty()){

                TreeNode pop = q.poll();
                int idx = qpos.poll();

                if(sb.length() >0) {
                    sb.append(",");
                }

                sb.append(idx+"_"+ pop.val);

                if(pop.left!=null){
                    q.add(pop.left);
                    qpos.add(idx*2+1);
                }

                if(pop.right!=null){
                    q.add(pop.right);
                    qpos.add(idx*2+2);
                }
            }

            return sb.toString();
        }
    }


    public static void main(String[] args) {
        TreeNode t= new TreeNode(2);
        t.left = new TreeNode(1);
        t.right = new TreeNode(3);

        Solution obj = new Solution();
        String str = obj.serialize(t);
        System.out.println(str);
    }
}


/*
https://www.lintcode.com/problem/1235/?showListFe=true&page=1&tagIds=371&pageSize=50

LintCode-Logo
搜索题目、标签、题集
中文
您上个月的个人报告已生成，点击查看
avatar
1235 · 序列化和反序列化二叉搜索树
算法
中等
通过率
66%

题目
题解22
笔记
讨论30
排名
记录
描述
序列化是将数据结构或对象转换为一系列位的过程，以便它可以存储在文件或内存缓冲区中，或通过网络连接链路传输，以便稍后在同一个或另一个计算机环境中重建。

设计一个算法来序列化和反序列化二叉搜索树。 对序列化/反序列化算法的工作方式没有限制。 您只需确保二叉搜索树可以序列化为字符串，并且可以将该字符串反序列化为最初的二叉搜索树。

编码的字符串应尽可能紧凑。

注意： 不要使用类成员/全局/静态变量来存储状态。 你的序列化和反序列化算法应该是无状态的。

样例
样例 1:

输入：{2,1,3}
输出：{2,1,3}
解释：
     2
    / \
   1   3
样例 2:

输入：{1,#,2}
输出：{1,#,2}
解释：
  1
   \
    2
标签
企业
Amazon
相关题目

7
二叉树的序列化和反序列化
中等
推荐课程

0基础入门数据分析
进阶大厂刚需高薪人才，熟练掌握SQL、Python、Tableau、A/Btest等实用技能工具，配套100+数据题夯实基础
39/133
已开启智能提示
发起考试
30 分 00 秒
1234567891011121314151617181920212223242526272829
/**
 * Definition of TreeNode:

控制台
        历史提交


 */
